package main

import "fmt"

func main() {
	matrix := [][]int{
		{1, 4, 7, 11, 15},
		{2, 5, 8, 12, 19},
		{3, 6, 9, 16, 22},
	}
	target := 5
	fmt.Println(searchMatrix(matrix, target))
}

//因为 matrix 矩阵中每行的元素从左到右升序排列且每列的元素从上到下升序排列，所以可以从左下角（或右上角）开始查找。
//若当前矩阵的元素值 == target，则直接返回 true。
//若当前矩阵的元素值 > target，则向上移动一行列不变，即 matrix[i][j] 变为 matrix[i - 1][j]，继续进行比较。
//若当前矩阵的元素值 < target，则向右移动一列行不变，即 matrix[i][j] 变为 matrix[i][j + 1]，继续进行比较。
func searchMatrix(matrix [][]int, target int) bool {
	i, j := len(matrix)-1, 0
	for i >= 0 && j < len(matrix[0]) {
		num := matrix[i][j]
		if num == target {
			return true
		} else if num > target {
			i--
		} else {
			j++
		}
	}
	return false
}
